The statements in this section merely provide background information related to the present disclosure and may not constitute prior art.
Image segmentation is a branch of digital image processing that performs the task of categorizing, or classifying, the elements of a digital image into one or more class types. The class types can correspond to objects within an image. Classifying elements in a digital image has permitted a new understanding of biology, physiology, anatomy, as well as facilitated studies of complex disease processes and medical diagnostic purposes in clinical care settings. Modern medicine and clinical care are particularly poised to benefit from greater imaging capabilities.
Initial volumetric images from may be provided from known imaging devices such as X-ray computed tomography (CT), magnetic resonance (MR), 3-D ultrasound, positron emission tomography (PET) and many other imaging devices. The imaging device typically provides a 3D image data set from which to perform image segmentation in typical medical imaging applications with the classification types related to anatomical structure. For example, in thoracic medical images, it is convenient to segment the image voxels into classes such as bone, lung parenchyma, soft tissue, bronchial vessels, blood vessels, etc. There are many reasons to perform such a task, such as surgical planning, treatment progress, and patient diagnosis.
Various known analytical techniques are utilized to perform image segmentation. One known technique includes analyzing 3-D medical images as sequences of 2-D image slices that form the 3-D data. This is undesirable as contextual slice-to-slice information is lacking when analyzing sequences of adjacent 2-D images. Performing the segmentation directly in the 3-D space tends to bring more consistent segmentation results, yielding object surfaces instead of sets of individual contours. 3-D image segmentation techniques—for example, techniques known by the terms region growing, level sets, fuzzy connectivity, snakes, balloons, active shape and active appearance models—are known. None of them, however, offers a segmentation solution that achieves optimal results. The desire for optimal segmentation of an organ or a region of pathology, for example, is critical in medical image segmentation.
Recently, graph-based approaches have been developed in medical image segmentation. A common theme of these graph-based approaches is the formation of a weighted graph in which each vertex is associated with an image pixel and each graph edge has a weight relative to the corresponding pixels of that edge to belong to the same object. The resulting graph is partitioned into components in a way that optimizes specified, preselected criteria of the segmentation.
When applied to graphs, the minimum s-t cut produces a partition of the graph at a mathematical optimal partition of two parts. There are many algorithms that have been developed to perform the minimum s-t cut of a graph. To date, the algorithms that have proven to have the greatest execution speed for performing the minimum s-t cut involve the simulation of flow through an analogous transportation or communication network. In this analogy, the weights of the edges of the graph are considered to be maximum allowable flows. A relatively new approach to the computation of the minimum s-t cut involves the use of numerical operations. Algorithms that use numerical operations for obtaining the minimum s-t cut or an approximation to the minimum s-t cut have been developed based on the linear programming methods.
Like other graph-based approaches, the energy minimization framework utilizing s-t cuts is fairly computationally complex when utilized in medical applications. Therefore, a need exists to more efficiently execute image segmentation using an energy-based framework utilizing s-t cuts of directed graphs that includes information about a direction in which the weight of a boundary at any point in the image depends on which side of the boundary is the inside and which side is the outside.